package com.leetcode.根据数据结构分类.数组;

/**
 * @author: ZhouBert
 * @date: 2021/1/18
 * @description: 240. 搜索二维矩阵 II
 * https://leetcode-cn.com/problems/search-a-2d-matrix-ii/
 */
public class B_240_搜索二维矩阵_II {

	public static void main(String[] args) {
		int target = 5;
		//int[][] matrix = {{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}};

//		int[][] matrix = {{-1, 3}};
//		target = 3;

		int[][] matrix = {{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17, 18, 19, 20}, {21, 22, 23, 24, 25}};
		target = 19;


		B_240_搜索二维矩阵_II action = new B_240_搜索二维矩阵_II();
		boolean res = action.searchMatrix(matrix, target);
		System.out.println("res = " + res);
	}

	/**
	 * 由于是升序序列，所以很容易就想到二分查找。
	 * --
	 * 刚开始以为列之间的数据也是升序的。想错了。
	 *
	 * @param matrix
	 * @param target
	 * @return
	 */
	public boolean searchMatrixForAllOrder(int[][] matrix, int target) {
		//行数
		int m = matrix.length;
		//列数
		int n = matrix[0].length;
		if (matrix[0][0] > target || matrix[m - 1][n - 1] < target) {
			return false;
		}

		//1.找到列 略小于 target 的 col
		int col = getCol(matrix[0], target);
		//2.找到行
		int begin = 0;
		int end = m;
		int mid = 0;
		while (begin < end) {
			mid = (begin + end) >> 1;
			if (matrix[mid][col] > target) {
				end = mid;
			} else if (matrix[mid][col] < target) {
				begin = mid + 1;
			} else {
				return true;
			}
		}
		return false;
	}

	/**
	 * 现在理解题意了
	 * 列跟列之间没有关系。——任何小于 target 的 col 中都是需要遍历的
	 * --
	 * 1.找到 minCol=0 maxCol（第一个大于 target 的位置）
	 * 2.再进行二分查找
	 * --
	 * 其实是不难的
	 * --
	 * 反思：
	 * 居然还有高超的二维数组的二分查找！
	 * 二维数组的遍历，蛇形走位！
	 * @param matrix
	 * @param target
	 * @return
	 */
	public boolean searchMatrix(int[][] matrix, int target) {
		//行数
		int m = matrix.length;
		//列数
		int n = matrix[0].length;
		if (matrix[0][0] > target || matrix[m - 1][n - 1] < target) {
			return false;
		}

		//记录最小的列和最大的列
		//int minCol = 0;
		int maxCol = getMaxCol(matrix[0], n, target);

		for (int i = 0; i < maxCol; i++) {
			int begin = 0, end = m, mid = 0;
			while (begin < end) {
				mid = (begin + end) >> 1;
				if (matrix[mid][i] > target) {
					end = mid;
				} else if (matrix[mid][i] < target) {
					begin = mid + 1;
				} else {
					return true;
				}
			}
		}
		return false;
	}


	/**
	 * 对于第一行的数据寻找稍小于 target 的索引
	 *
	 * @param array
	 * @return
	 */
	private int getCol(int[] array, int target) {
		int begin = 0;
		int end = array.length;
		if (target > array[end - 1]) {
			return end - 1;
		}

		int mid = 0;
		while (begin < end) {
			mid = (begin + end) >> 1;
			if (array[mid] > target) {
				end = mid;
			} else if (array[mid] < target) {
				begin = mid + 1;
			} else {
				return mid;
			}
		}
		//此时找到最接近的数
		if (array[begin] > target) {
			return begin - 1;
		} else {
			return begin;
		}
	}

	/**
	 * 开区间
	 *
	 * @return
	 */
	private int getMaxCol(int[] array, int len, int target) {
		int begin = 0, end = len, mid = 0;
		while (begin < end) {
			mid = (begin + end) >> 1;
			if (array[mid] > target) {
				end = mid;
			} else if (array[mid] < target) {
				begin = mid + 1;
			} else {
				return mid + 1;
			}
		}
		return end;
	}
}
